#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 1000000000  // 支持 n = 1e8，实际可更大
#define BIT_ARR_SIZE(n) (((n)+7)/8)

uint8_t is_prime[BIT_ARR_SIZE(MAXN+1)];
int primes[MAXN / 10];
int prime_count = 0;

// 访问第i位（0表示false，1表示true）
#define GET_BIT(arr, i) (((arr)[(i)>>3] >> ((i)&7)) & 1)
#define SET_BIT(arr, i) ((arr)[(i)>>3] |=  (1<<((i)&7)))
#define CLR_BIT(arr, i) ((arr)[(i)>>3] &= ~(1<<((i)&7)))

// 初始化全部为1（素数）
void bit_arr_set_all(uint8_t *arr, int n) {
    memset(arr, 0xFF, BIT_ARR_SIZE(n));
}

int main() {
    int n;
    printf("请输入要求的最大值 n（建议<=1e8）：");
    scanf("%d", &n);

    bit_arr_set_all(is_prime, n+1);
    CLR_BIT(is_prime, 0); // 0不是素数
    CLR_BIT(is_prime, 1); // 1不是素数

    // 欧拉筛
    for (int i = 2; i <= n; ++i) {
        if (GET_BIT(is_prime, i)) {
            primes[prime_count++] = i;
        }
        for (int j = 0; j < prime_count; ++j) {
            int p = primes[j];
            if (i * p > n) break;
            CLR_BIT(is_prime, i * p); // 标记合数
            if (i % p == 0) break;
        }
    }

    printf("2~%d内的所有素数：\n", n);
    for (int i = 0; i < prime_count; ++i) {
        printf("%d\n", primes[i]);
    }
    printf("共计 %d 个素数。\n", prime_count);

    return 0;
}